package someTestExcemple.huaweiOd.container.tree.bfsOrDfs;
//华为OD机试 - 战场索敌 - 深度优先搜索dfs算法（Java 2025 A卷 100分）
//https://blog.csdn.net/guorui_java/article/details/132524247
import java.util.*;

public class SearchEnemy {
    private static boolean[][] visited;
    private static int[][] directions = {{-1,0},{0,1},{1,0},{0,-1}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input1 = sc.nextLine().split(" ");
        int N = Integer.parseInt(input1[0]); //战场行数
        int M = Integer.parseInt(input1[1]); //战场列数
        int K = Integer.parseInt(input1[2]); //k
        char[][] battlefield = new char[N][M];
        visited = new boolean[N][M]; //每个元素是否已经访问过
        for(int i=0;i<N;i++) {
            battlefield[i] = sc.nextLine().toCharArray();
        }
        System.out.println(Arrays.deepToString(battlefield));
        int blockCount=0;
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                if(battlefield[i][j] =='#' || visited[i][j]) {
                    continue;
                }
                //当前区域不是墙壁且没被访问过 ，进行dfs搜索当前区域所有敌人数量
                if(dfs(i,j,N,M,battlefield) > K) {
                    blockCount++;
                }
            }
        }
        System.out.println(blockCount);

    }
    public static int dfs(int x,int y,int N,int M,char[][] battlefield) {
        visited[x][y] = true;
        //上下左右再进行dfs
        int enemy_num =0;
        //该位置有敌人
        if(battlefield[x][y]=='E') {
            enemy_num++;
        }
        for(int i=0;i<directions.length;i++) {
            int newX = x+directions[i][0];
            int newY = y+directions[i][1];
            if(newX >=0 && newX<N && newY>=0 && newY<M  && !visited[newX][newY] && battlefield[newX][newY] !='#') {
                //新位置没被访问过且不是墙
               enemy_num += dfs(newX,newY,N,M,battlefield);
            }
        }
        return  enemy_num;
    }
}
